home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Experimental BBS Explossion 3
/
Experimental BBS Explossion III.iso
/
c
/
cp1.zip
/
INDEX.C
< prev
next >
Wrap
C/C++ Source or Header
|
1993-05-12
|
5KB
|
157 lines
===========================================================================
BBS: The Abacus * HST/DS * Potterville MI
Date: 05-09-93 (14:13) Number: 30
From: MARK CORGAN Refer#: NONE
To: ALL Recvd: NO
Subj: INDEX.C Conf: (36) C Language
---------------------------------------------------------------------------
Hello All!
The following two mesages are the index and the look-up functions for creating a
nd searching binary trees. INDEX.C creates a binary file from a formatted ascii
file whose format is described in the next message. Each record is stored in alp
habetical order. LOOKUP.C uses the bsearch() function to find a record in the bi
nary file and then prints the information to the screen.
This code is hereby donated to the public domain.
/* INDEX.C */
#include <stdio.h>
#include "defines.h" /* definitions for INDEX and LOOKUP */
struct tree_node /* node in tree */
{
struct tree_node *l_ptr, *r_ptr; /* left and right pointers */
INDEX *data_ptr; /* data pointer */
};
typedef struct tree_node TREE_NODE;
void write_index(void);
void save_tree(TREE_NODE * root, FILE *fp);
TREE_NODE *make_tree(FILE *fp, long *cnt_ptr);
TREE_NODE *insert_tree(TREE_NODE *root, INDEX *rec_ptr, long *cnt_ptr);
FILE *my_fopen(char *file_name, char *mode);
long bsearch(FILE *ifp, long first, long last, char *target);
void main(void)
{
write_index();
}
void write_index(void)
{
FILE *afp, *ifp; /* types of files */
TREE_NODE *root; /* index tree */
static INDEX header = {"!", 0}; /* dummy header node */
afp = my_fopen(ASCII_FILE, "r");
if((root = make_tree(afp, &header.pos)) != NULL)
{
ifp = my_fopen(INDEX_FILE, "wb");
fwrite((char *) &header, sizeof(header), 1, ifp);
save_tree(root, ifp);
fclose(ifp);
printf("\n%ld records\n", header.pos);
}
fclose(afp);
}
/* Make index tree */
TREE_NODE *make_tree(FILE *fp, long *cnt_ptr) /* file & count of records */
{
TREE_NODE *root = NULL, *temp_ptr; /* add node to tree */
char line[MAX_LINE]; /* next line */
long start_pos = 0;
INDEX *next_ptr; /* next key, pos pair */
BOOLEAN new_record = TRUE, have_mem = TRUE; /* starting with new record */
*cnt_ptr = 0;
while(start_pos = ftell(fp), have_mem && fgets(line,sizeof(line), fp))
{
if(new_record)
{
if((next_ptr = (INDEX *) malloc(sizeof(INDEX))) != NULL)
{
strncpy(next_ptr->key, line, MAX_KEY);
next_ptr->pos = start_pos;
if((temp_ptr = insert_tree(root, next_ptr, cnt_ptr)) != NULL)
root = temp_ptr;
}
have_mem = next_ptr && temp_ptr;
}
new_record = strcmp(line, END_REC) == 0;
}
if(!have_mem)
fprintf(stderr, "Out of memory. Key: %s\n", line);
return root;
}
/* save the index tree to a file */
void save_tree(TREE_NODE *root, FILE *fp)
{
if(root)
{
save_tree(root->l_ptr, fp);
fwrite(root->data_ptr, sizeof(INDEX), 1, fp);
save_tree(root->r_ptr, fp);
}
}
/* add record to tree */
/* pointer to tree, record to install, nodes in tree */
TREE_NODE *insert_tree(TREE_NODE *root, INDEX *rec_ptr, long *cnt_ptr)
{
if(root)
{
int cmp = strncmp(rec_ptr->key, root->data_ptr->key, MAX_KEY);
if(cmp < 0) /* left side? */
root->l_ptr = insert_tree(root->l_ptr, rec_ptr, cnt_ptr);
else if(cmp > 0) /* right side */
root->r_ptr = insert_tree(root->r_ptr, rec_ptr, cnt_ptr);
else
fprintf(stderr, "Duplicate key: %s\n", rec_ptr->key);
}
else if(root = (TREE_NODE *) malloc(sizeof(TREE_NODE)), root)
{
root->data_ptr = rec_ptr;
root->l_ptr = root->r_ptr = NULL;
(*cnt_ptr)++;
}
return root;
}
long bsearch(FILE *ifp, long first, long last, char *target)
{
long pos, mid =(first + last) / 2;
INDEX next;
int cmp;
if(mid < first || fseek(ifp, mid * sizeof(INDEX), 0) != 0 ||
fread((char *) &next, sizeof(INDEX), 1, ifp) == 0)
pos = -1;
else
pos = ((cmp = strncmp(target, next.key, MAX_KEY)) == 0)
? next.pos
: ((cmp < 0) ? bsearch(ifp, first, mid - 1, target)
: bsearch(ifp, mid + 1, last, target));
return pos;
}
FILE *my_fopen(char *file_name, char *mode)
{
FILE *fp = fopen(file_name, mode);
if(!fp)
{
fprintf(stderr, "Can't open file \"%s\" for %s\n", file_name,
(*mode == 'r')
? "reading"
: ((*mode == 'w') ? "writing" : "appending"));
exit(1);